package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-19
 */

import java.util.ArrayList;

/**
 * 最大路径和加打印路径
 */
public class leetcode124_2 {
    int ans = Integer.MIN_VALUE;
    ArrayList<Integer> res = new ArrayList<>();
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    public int dfs(TreeNode root){
        //叶子节点以下的节点只能返回0
        if (root==null) return 0;

        //left表示root的左叶子节点能给root的最大贡献，right同理
        //所求的值即为 一个节点+左子节点最大贡献+右子节点最大贡献
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (root.val+left+right>ans){
            ans = root.val+left+right;
            res.add(root.val);
        }
        int max = Math.max(left,right)+root.val;
        return max<0? 0:max;
    }
}
